#include <stack>
#include <vector>
#include <string>
#include <iostream>

using namespace std;

class Solution 
{
public:
    int evalRPN(vector<string>& tokens) 
    {
        if(tokens.empty())
        {
            return 0;
        }
        stack<int> st;
        for(int i = 0; i < tokens.size(); i++)
        {
            if(tokens[i] == "+")
            {
                int num1 = st.top();
                st.pop();
                int num2 = st.top();
                st.pop();
                st.push(num2 + num1);
            }
            else if (tokens[i] == "-")
            {
                int num1 = st.top();
                st.pop();
                int num2 = st.top();
                st.pop();
                st.push(num2 - num1);
            }
            else if(tokens[i] == "*")
            {
                int num1 = st.top();
                st.pop();
                int num2 = st.top();
                st.pop();
                st.push(num2 * num1);
            }
            else if (tokens[i] == "/")
            {
                int num1 = st.top();
                st.pop();
                int num2 = st.top();
                st.pop();
                st.push(num2 / num1);
            }
            else
            {
                st.push(stoi(tokens[i]));
            }
        }
        if(st.empty())
        {
            return 0;
        }
        return st.top();
    }
};

int main()
{
    Solution solution;

    // 测试案例1: 简单加法
    vector<string> test1 = {"2", "1", "+", "3", "*"};
    cout << "测试案例1: ";
    for (const string& token : test1) {
        cout << token << " ";
    }
    cout << endl;
    cout << "结果: " << solution.evalRPN(test1) << endl;
    cout << "预期: 9" << endl << endl;

    // 测试案例2: 减法和除法
    vector<string> test2 = {"4", "13", "5", "/", "+"};
    cout << "测试案例2: ";
    for (const string& token : test2) {
        cout << token << " ";
    }
    cout << endl;
    cout << "结果: " << solution.evalRPN(test2) << endl;
    cout << "预期: 6" << endl << endl;

    // 测试案例3: 复杂表达式
    vector<string> test3 = {"10", "6", "9", "3", "+", "-11", "*", "/", "*", "17", "+", "5", "+"};
    cout << "测试案例3: ";
    for (const string& token : test3) {
        cout << token << " ";
    }
    cout << endl;
    cout << "结果: " << solution.evalRPN(test3) << endl;
    cout << "预期: 22" << endl << endl;

    // 测试案例4: 单个数字
    vector<string> test4 = {"42"};
    cout << "测试案例4: ";
    for (const string& token : test4) {
        cout << token << " ";
    }
    cout << endl;
    cout << "结果: " << solution.evalRPN(test4) << endl;
    cout << "预期: 42" << endl << endl;

    // 测试案例5: 乘法和除法
    vector<string> test5 = {"3", "11", "+", "2", "*"};
    cout << "测试案例5: ";
    for (const string& token : test5) {
        cout << token << " ";
    }
    cout << endl;
    cout << "结果: " << solution.evalRPN(test5) << endl;
    cout << "预期: 28" << endl << endl;

    // 测试案例6: 负数和除法
    vector<string> test6 = {"-5", "2", "*"};
    cout << "测试案例6: ";
    for (const string& token : test6) {
        cout << token << " ";
    }
    cout << endl;
    cout << "结果: " << solution.evalRPN(test6) << endl;
    cout << "预期: -10" << endl << endl;

    return 0;
}